import random


"""
    二分法
    1. 查找列表中值是否存在
"""
def is_in(arr: list, value: int, start: int, end: int):
    """ 递归写法 """
    # 取中键位置
    index = int((start + end)/2)
    # 递归出口
    if start > end:
        return None
    # 如果值小于中间值
    if value < arr[index]:
        # 结束位置移动到中间位置减一
        end = index - 1
    elif value > arr[index]:
        # 起始位置移动到中间位置加一
        start = index + 1
    else:
        return index
    return is_in(arr, value, start, end)


def circulation(arr: list, value: int, start: int, end: int):
    """ 非递归写法 """
    while start <= end:
        index = int((start + end)/2)
        # 如果值小于中间值
        if value < arr[index]:
            # 结束位置移动到中间位置减一  ----》 减一加一的方式可以避免13 14 不断循环
            end = index - 1
        elif value > arr[index]:
            # 起始位置移动到中间位置加一
            start = index + 1
        else:
            return index
    return None

def main():
    ### 对数器生成有序的随机序列
    arr = []
    for i in range(random.randint(10, 20)):
        value = random.randint(0, 100)
        arr.append(value)
    arr = sorted(arr)
    return arr


if __name__ == "__main__":
    for i in range(1000):
        arr = main()
        value = random.randint(0, 100)
        res = is_in(arr, value, 0, len(arr)-1)
        cir_res = circulation(arr, value, 0, len(arr)-1)
        if res != cir_res:
            print("res:", res, "cir_res:", cir_res)
            print(arr)
            print(value)
            break
        print(res)


